package com.atwulidun.recursion;

public class EightQueens {
    private static int max = 8;// 定义皇后的数量
    private static int[] arr = new int[8];// 皇后摆放的方式，数组的下标表示行，该下标对应的数组元素的值表示列
    private static int num;

    public static void main(String[] args) {
        backTrack(0, 0, max);
        System.out.println(num);
    }

    // 判断当前摆放的皇后和之前已经摆放的皇后是否冲突的方法(减枝方法)
    // 注意：调用该方法的前提是arr[n]已经赋了值
    public static boolean isUnconfilicted(int n) {
        for (int i = 0; i < n; i++) {
            if (arr[i] == arr[n] || Math.abs(i - n) == Math.abs(arr[i] - arr[n])) {
                return false;// 有冲突
            }
        }
        return true;// 没有冲突
    }

    // 回溯方法

    /**
     * @param n     代表当前皇后的行
     * @param start 代表可供选择的列的范围头
     * @param end   代表可供选择的列的范围尾
     */
    public static void backTrack(int n, int start, int end) {
        // 递归结束条件
        if (n == max) {
            for (int j : arr) {
                System.out.print(j + " ");
            }
            System.out.println();
            num++;
            return;
        }
        // 对摆放的列进行选择
        for (int i = start; i < end; i++) {
            // 选择
            arr[n] = i;
            // 进行减枝判断，不冲突才摆放下一个
            // 注意：调用isUnconfilicted方法的前提是arr[n]已经赋了值
            if (isUnconfilicted(n)) {
                // 递归：摆放下一行
                backTrack(n + 1, start, end);
            }
            // 撤销选择
            arr[n] = 0;// 其实这里撤不撤销都无所谓，因为下一次选择又会对arr[n]进行赋值，覆盖掉之前的值
        }
    }
}
